#include <iostream>
#include <cmath>
#include "prime.h"

// Find all progressive numbers.
template <class Func>
static void find_progressive_numbers(long long N, Func f)
{
	// Special case: r = 1
	for (long long q = 2; ; q++)
	{
		long long n = q*q*q+1;
		if (n > N)
			break;
		f(n);
	}

	// For each r >= 2, r must divide q^2, and q must be greater than r.
	for (int r = 2; (long long)r * r < N; r++)
	{
		int base = 1;
		prime_factorize_distinct(r, [&base](int p, int k) {
			for (int i = (k-1)/2; i >= 0; --i)
				base *= p;
		});
		for (int q = (r / base + 1) * base; ; q += base)
		{
			long long p = (long long)q * q / r;
			long long n = p * q + r;
			if (n > N)
				break;
			f(n);
		}
	}
}

static int count_progressive_numbers(long long N)
{
	int count = 0;
	find_progressive_numbers(N, [&count](long long n) { ++count; });
	return count;
}

static long long sum_progressive_squares(long long N)
{
	long long sum = 0;
	find_progressive_numbers(N, [&sum](long long n) {
		long long root = (long long)std::sqrt((double)n);
		if (root * root == n)
			sum += n;
	});
	return sum;
}

void solve_problem_141()
{
#if 0
	const long long N = 99999;
#else
	const long long N = 999999999999LL;
#endif
	
	std::cout << sum_progressive_squares(N) << std::endl;

#if 0
	for (long long N = 10; N <= 1000000000000LL; N *= 10)
	{
		std::cout << N << " " << count_progressive_numbers(N) << std::endl;
	}	
#endif
}
